﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    public class Matrix
    {
        private double[,] _matrix;
        public Matrix(double[,] matrix)
        {
            this._matrix = matrix;
            this.RowLen = (int)this._matrix.GetLongLength(0) ;
            this.ColLen =(int) this._matrix.GetLongLength(1);
        }

        public double this[int r, int c]
        {
            get
            {
                return this._matrix[r, c];
            }
            set
            {
                this._matrix[r, c] = value;
            }
        }

        /// <summary>
        /// 矩阵列长
        /// </summary>
        public int ColLen
        {
            get;
            private set;
        }

        /// <summary>
        /// 矩阵行宽
        /// </summary>
        public int RowLen
        {
            get;
            private set;
        }

        /// <summary>
        /// 没有实现
        /// </summary>
        /// <returns></returns>
        public Matrix InverseMatrix()
        {
            return null;
        }

        /// <summary>
        /// 矩阵乘法 n^3
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public Matrix Multiply(Matrix matrix)
        {
            double[,] result = new double[this.RowLen, matrix.ColLen];
            if (this.ColLen != matrix.RowLen)
            {
                throw new Exception("Can not Multiply.");
            }
            else
            {
                for (int r = 0; r < this.RowLen; r++)
                {
                    for (int c = 0; c < matrix.ColLen; c++)
                    {
                        result[r, c] = 0;
                        for (int i = 0; i < this.ColLen; i++)
                        {
                            result[r, c] = result[r, c] + this[r, i] * matrix[i,c];
                        }
                    }
                }
            }

            return new Matrix(result);
        }

        /// <summary>
        /// 矩阵加法
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public Matrix Add(Matrix matrix)
        {
            double[,] result = new double[this.RowLen, matrix.ColLen];
            if (this.ColLen != matrix.ColLen || this.RowLen != matrix.RowLen)
            {
                throw new Exception("Can not Add.");
            }
            else
            {
                for (int r = 0; r < this.RowLen; r++)
                {
                    for (int c = 0; c < matrix.ColLen; c++)
                    {
                        result[r, c] = this[r, c] + matrix[r, c];
                    }
                }
            }

            return new Matrix(result);
        }


        /// <summary>
        /// 矩阵减法
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public Matrix Sub(Matrix matrix)
        {
            double[,] result = new double[this.RowLen, matrix.ColLen];
            if (this.ColLen != matrix.ColLen || this.RowLen != matrix.RowLen)
            {
                throw new Exception("Can not Sub.");
            }
            else
            {
                for (int r = 0; r < this.RowLen; r++)
                {
                    for (int c = 0; c < matrix.ColLen; c++)
                    {
                        result[r, c] = this[r, c] - matrix[r, c];
                    }
                }
            }

            return new Matrix(result);
        }

        /// <summary>
        /// 备忘录方法，计算代价
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        private static double Menoized_Matrix_Chain(int[] p)
        {
            var len = p.Length - 1;
            double[,] m = new double[len, len];
            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < len; j++)
                {
                    m[i, j] = double.MaxValue;
                }
            }
            return lookup_china(m, 0, len-1);
        }

        private static double lookup_china(double[,] m, int i, int j)
        {
            if (m[i, j] < double.MaxValue)
            {
                return m[i, j];
            }
            if (i == j)
            {
                m[i, j] = 0;
            }
            else
            {
                for (int k = i; k < j; k++)
                {
                    var v = lookup_china(m,i, k) + lookup_china(m, k + 1, j);
                    if (v < m[i, j])
                    {
                        m[i, j] = v;
                    }
                }
            }
            return m[i, j];
        }

        /// <summary>
        /// 辅助方法，确定分割点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        private static int[,] Matrix_Chain_Order(int[] p)
        {
            var matrixLen = p.Length - 1;
            double[,] m = new double[matrixLen,matrixLen];
            for (int i = 0; i < matrixLen; i++)
            {
                m[i, i] = 0;
            }

            int[,] s = new int[matrixLen, matrixLen];

            for (int len = 2; len <= matrixLen; len++)
            {
                for (int i = 0; i <= matrixLen - len ; i++)
                {
                    var j = i + len -1;
                    m[i, j] = double.MaxValue;
                    for (int k = i; k < j; k++)
                    {
                        var q = m[i, k] + m[k + 1, j] + p[i] * p[k+1] * p[j];
                        if (q < m[i, j])
                        {
                            m[i, j] = q;
                            s[i, j] = k;
                        }
                    }
                }
            }

            return s;
        }

        public static Matrix UnitMatrix(int dimension)
        {
            double[,] d = new double[dimension, dimension];
            for (int i = 0; i < dimension; i++)
            {
                d[i, i] = 1;
            }
            return new Matrix(d);
        }

        /// <summary>
        /// 快速矩阵乘法
        /// </summary>
        /// <param name="matrixs"></param>
        /// <returns></returns>
        public static Matrix FastMultiply(params Matrix[] matrixs)
        {
            int[] p = new int[matrixs.Length + 1];
            for (int i = 0; i < matrixs.Length; i++)
            {
                p[i] = matrixs[i].RowLen;
                p[i + 1] = matrixs[i].ColLen;
            }

            var s = Matrix_Chain_Order(p);

            return Multiply(matrixs, s, 0, matrixs.Length - 1);
        }

        /// <summary>
        /// 递归遍历乘法
        /// </summary>
        /// <param name="matrixs"></param>
        /// <param name="s"></param>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        private static Matrix Multiply(Matrix[] matrixs, int[,] s, int i, int j)
        {
            if (i >= j)
            {
                return matrixs[i];
            }
            else
            {
                return Multiply(matrixs, s, i, s[i, j]).Multiply(Multiply(matrixs, s, s[i, j] + 1, j));
            }
        }
    }
}
